{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\n    程序 = 数据结构 + 算法\\n'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "    程序 = 数据结构 + 算法\n",
    "    \n",
    "    算法五大特性\n",
    "    1、输入\n",
    "    2、输出\n",
    "    3、有穷：有结束条件\n",
    "    4、确定性：每一步都有意义\n",
    "    5、可行性：能用代码写出来\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\n    时间复杂度：\\n        O(n) 表示程序的循环次数是n， 比如for i in range(n)\\n    常见的复杂度排序：\\n        O(1)\\n        O(log(n))\\n        O(n)\\n        O(n*log(n))\\n        O(n^2)\\n        O(n^3)\\n        O(2^n)\\n    空间复杂度：\\n        S(n) 是对一个算法在运行过程中临时占用存储空间大小的量度。\\n        S(1) 临时存储空间（堆栈）不随被处理数据量n的大小而改变。\\n        ...\\n    \\n'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "    时间复杂度：\n",
    "        O(n) 表示程序的循环次数是n， 比如for i in range(n)\n",
    "    常见的复杂度排序：\n",
    "        O(1)\n",
    "        O(log(n))\n",
    "        O(n)\n",
    "        O(n*log(n))\n",
    "        O(n^2)\n",
    "        O(n^3)\n",
    "        O(2^n)\n",
    "    空间复杂度：\n",
    "        S(n) 是对一个算法在运行过程中临时占用存储空间大小的量度。\n",
    "        S(1) 临时存储空间（堆栈）不随被处理数据量n的大小而改变。\n",
    "        ...\n",
    "    \n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+       1.2117927219789593 ms\n",
      "append  1.093579920048379 ms\n",
      "[]      0.44177139434058077 ms\n",
      "list()  0.23304896482162718 ms\n",
      "extend  1.449354681072446 ms\n",
      "+=      1.742595202106255 ms\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "python 内置类型性能分析\n",
    "\n",
    "'''\n",
    "import timeit\n",
    "\n",
    "# 列表list\n",
    "def test1():\n",
    "    l = []\n",
    "    for i in range(10000):\n",
    "        l += [i]\n",
    "\n",
    "# append() 接收参数是元素或者列表，往尾部插入\n",
    "def test2():\n",
    "    l = []\n",
    "    for i in range(10000):\n",
    "        l.append(i)\n",
    "\n",
    "# 列表生成器效率也可以\n",
    "def test3():\n",
    "    l = [i for i in range(10000)]\n",
    "    \n",
    "# 效率最高\n",
    "def test4():\n",
    "    list(range(10000))\n",
    "    \n",
    "# extend() 接收参数是一个列表\n",
    "# 把列表拍平，变成一个列表\n",
    "# 效率比append低\n",
    "def test5():\n",
    "    l = []\n",
    "    for i in range(10000):\n",
    "        l.extend([i])\n",
    "\n",
    "# 往头部插入是最慢的，因为每往头部插入一个元素\n",
    "# 整个列表就往后移一位\n",
    "def test6():\n",
    "    l = []\n",
    "    for i in range(10000):\n",
    "        l.insert(0,i)\n",
    "    \n",
    "# l = l + [i]   这条语句执行想当慢284ms，比如extend要慢很多，为啥？因为这里是涉及到list拷贝，如果是+=表示直接在l上操作。\n",
    "def test7():\n",
    "    l = []\n",
    "    for i in range(10000):\n",
    "        l = l + [i]\n",
    "\n",
    "'''\n",
    "python内置的程序执行效率分析器 timeit\n",
    "\n",
    "timeit接收三个参数，\n",
    "第一个参数是要测试的python语句\n",
    "第二个参数是执行python语句的前提条件， 比如import xxx, import __main__等等\n",
    "\n",
    "第三个参数是指定执行的次数number，默认的执行时间事100w，也可以自己指定\n",
    "返回值是number次数的平均执行ms。\n",
    "\n",
    "'''\n",
    "print(\"+      \",timeit.timeit(\"test1()\", setup=\"from __main__ import test1\", number=1000), \"ms\")\n",
    "print(\"append \",timeit.timeit(\"test2()\", setup=\"from __main__ import test2\", number=1000), \"ms\")\n",
    "print(\"[]     \",timeit.timeit(\"test3()\", setup=\"from __main__ import test3\", number=1000), \"ms\")\n",
    "print(\"list() \",timeit.timeit(\"test4()\", setup=\"from __main__ import test4\", number=1000), \"ms\")\n",
    "print(\"extend \",timeit.timeit(\"test5()\", setup=\"from __main__ import test5\", number=1000), \"ms\")\n",
    "# print(\"insert \",timeit.timeit(\"test6()\", setup=\"from __main__ import test6\", number=1000), \"ms\")\n",
    "# print(\"+=     \",timeit.timeit(\"test7()\", setup=\"from __main__ import test7\", number=1000), \"ms\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\ncopy               O(n)\\nget                O(1)\\nset                O(1)\\ndel                O(1)\\ncontains           O(1)\\niterator           O(n)\\n'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# list 列表\n",
    "'''\n",
    "list的常见操作时间复杂度\n",
    "\n",
    "index[]              O(1)\n",
    "insert assignment()  O(1)\n",
    "append()             O(1)\n",
    "pop()                O(1)\n",
    "pop(i)               O(n)\n",
    "insert(i, item)      O(n)\n",
    "delete()             O(n)\n",
    "iterator()          O(n)\n",
    "contain()           O(n)\n",
    "[:]                 O(k)\n",
    "del[:]              O(n)\n",
    "reverse()           O(n)\n",
    "sort()              O(n*log(n))\n",
    "multiply()          O(nk)\n",
    "'''\n",
    "\n",
    "# dict 字典\n",
    "'''\n",
    "copy               O(n)\n",
    "get                O(1)\n",
    "set                O(1)\n",
    "del                O(1)\n",
    "contains           O(1)\n",
    "iterator           O(n)\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "'''\n",
    " 数据结构\n",
    "     基本数据存储的组合形式。\n",
    " ADT 抽象数据类型，就是把一些操作放在一起，至于具体实现不用管，可以理解为抽象类。\n",
    " 最常用的ADT操作：\n",
    "     增加\n",
    "     删除\n",
    "     修改\n",
    "     查询\n",
    "     排序\n",
    "'''\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
